1. Field of the Invention
The invention pertains generally to computers. In particular, it pertains to processing exponents electronically using an improved square-and-multiply technique.
2. Description of the Related Art
Several computer applications involve exponentiation, or the process of raising a base number to a power, where the exponent is a very large number. This is particularly true in some encryption/decryption schemes, such as the well-known Rivest-Shamir-Adleman (RSA) approach to public key encryption. The security of this system increases as the number of bits in the exponents increases. Current RSA implementations of public key encryption commonly use exponents with 1024 bits. As increasingly powerful computers become available for code-breaking efforts, the size of these numbers will most likely increase even more to maintain the same level of security.
The square-and-multiply technique has been developed to more efficiently process exponentiation when using binary numbers. In the conventional approach to this technique, each bit of the exponent is examined sequentially, starting with the most significant bit (MSB), and the current value of the process is operated on. Before starting, the base number (the number being raised to a power) represents the current value; after that, the result of the previous operation represents the current value. If the bit being examined in the exponent is a zero, the current value of the process is squared. If the bit being examined is a one, the current value of the process is both squared and multiplied by the original base number. The number of operations involved in this process equals the total number of bits in the exponent, plus the number of xe2x80x981xe2x80x99 bits in the exponent, minus one. Thus, the average number of operations for a 1024-bit exponent would be 1535, assuming an equal number of ones and zeros in the average exponent. Since the base number typically involves large numbers in an encryption algorithm, each operation is a large and potentially time-consuming step if implemented in hardware, and even more time-consuming if implemented in software. The time to execute a conventional square-and-multiply approach increases linearly with the number of bits in the exponent, which can become a bottleneck in response times for those applications that use RSA encryption in interactive communications or other time-sensitive applications.